package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

public class _offer_55_2_balance_tree {
    
    /**
     * 为啥一道简单题标记成中等
     *
     * 这个写法，效率不高据说
     *
     * */
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return isBalanced(root.left) && isBalanced(root.right) && Math.abs(height(root.left) - height(root.right)) <= 1;
    }
    
    int height(TreeNode node) {
        if (node == null) return 0;
        return Math.max(height(node.left), height(node.right)) + 1;
    }
    
    /**
     * 这个解法不是正常人能想出来的
     *
     * */
    public boolean isBalanced2(TreeNode root) {
        return height2(root) != -1;
    }
    
    /**
     * @return -1 when not balanced else return height
     * */
    int height2(TreeNode node) {
        if (node == null) return 0;
        int left = height2(node.left);
        if (left == -1) return -1;
        int right = height2(node.right);
        if (right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
    
}
